/*
 * Copyright (c) Kumo Inc. and affiliates.
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <functional>

#include <melon/cportability.h>
#include <melon/conv.h>
#include <melon/format.h>
#include <melon/likely.h>
#include <melon/portability.h>
#include <melon/detail/iterators.h>
#include <melon/lang/exception.h>

namespace melon {
    namespace detail {
        struct DynamicHasher {
            using is_transparent = void;
            using melon_is_avalanching = std::true_type;

            size_t operator()(Dynamic const &d) const { return d.hash(); }

            template<typename T>
            std::enable_if_t<std::is_convertible<T, StringPiece>::value, size_t>
            operator()(T const &val) const {
                // keep consistent with Dynamic::hash() for strings
                return Hash()(static_cast<StringPiece>(val));
            }
        };

        struct DynamicKeyEqual {
            using is_transparent = void;

            bool operator()(const Dynamic &lhs, const Dynamic &rhs) const {
                return std::equal_to<Dynamic>()(lhs, rhs);
            }

            // Dynamic objects contains a map<Dynamic, Dynamic>. At least one of the
            // operands should be a Dynamic. Hence, an operator() where both operands are
            // convertible to StringPiece is unnecessary.
            template<typename A, typename B>
            std::enable_if_t<
                std::is_convertible<A, StringPiece>::value &&
                std::is_convertible<B, StringPiece>::value,
                bool>
            operator()(A const &lhs, B const &rhs) const = delete;

            template<typename A>
            std::enable_if_t<std::is_convertible<A, StringPiece>::value, bool> operator()(
                A const &lhs, Dynamic const &rhs) const {
                return MELON_LIKELY(rhs.type() == Dynamic::Type::STRING) &&
                       std::equal_to<StringPiece>()(lhs, rhs.stringPiece());
            }

            template<typename B>
            std::enable_if_t<std::is_convertible<B, StringPiece>::value, bool> operator()(
                Dynamic const &lhs, B const &rhs) const {
                return MELON_LIKELY(lhs.type() == Dynamic::Type::STRING) &&
                       std::equal_to<StringPiece>()(lhs.stringPiece(), rhs);
            }
        };
    } // namespace detail
} // namespace melon

//////////////////////////////////////////////////////////////////////

/* clang-format off */
// This is a higher-order preprocessor macro to aid going from runtime
// types to the compile time type system.

#define FB_DYNAMIC_APPLY(type, apply)                                             \
  do {                                                                            \
    MELON_PUSH_WARNING MELON_CLANG_DISABLE_WARNING("-Wcovered-switch-default")    \
    switch ((type)) {                                                             \
      case NULLT:                                                                 \
        apply(std::nullptr_t);                                                    \
        break;                                                                    \
      case ARRAY:                                                                 \
        apply(Array);                                                             \
        break;                                                                    \
      case BOOL:                                                                  \
        apply(bool);                                                              \
        break;                                                                    \
      case DOUBLE:                                                                \
        apply(double);                                                            \
        break;                                                                    \
      case INT64:                                                                 \
        apply(int64_t);                                                           \
        break;                                                                    \
      case OBJECT:                                                                \
        apply(ObjectImpl);                                                        \
        break;                                                                    \
      case STRING:                                                                \
        apply(std::string);                                                       \
        break;                                                                    \
      default:                                                                    \
        abort();                                                                  \
    }                                                                             \
    MELON_POP_WARNING                                                             \
  } while (0)
/* clang-format on */
//////////////////////////////////////////////////////////////////////

namespace melon {
    struct MELON_EXPORT TypeError : std::runtime_error {
        explicit TypeError(const std::string &expected, Dynamic::Type actual);

        explicit TypeError(
            const std::string &expected,
            Dynamic::Type actual1,
            Dynamic::Type actual2);
    };

    //////////////////////////////////////////////////////////////////////

    namespace detail {
        // This helper is used in destroy() to be able to run destructors on
        // types like "int64_t" without a compiler error.
        struct Destroy {
            template<class T>
            static void destroy(T *t) {
                t->~T();
            }
        };

        /*
         * Helper for implementing numeric conversions in operators on
         * numbers.  Just promotes to double when one of the arguments is
         * double, or throws if either is not a numeric type.
         */
        template<template <class> class Op>
        Dynamic numericOp(Dynamic const &a, Dynamic const &b) {
            if (!a.isNumber() || !b.isNumber()) {
                throw_exception<TypeError>("numeric", a.type(), b.type());
            }
            if (a.isDouble() || b.isDouble()) {
                return Op<double>()(a.asDouble(), b.asDouble());
            }
            return Op<int64_t>()(a.asInt(), b.asInt());
        }
    } // namespace detail

    //////////////////////////////////////////////////////////////////////

    /*
     * We're doing this instead of a simple member typedef to avoid the
     * undefined behavior of parameterizing F14NodeMap<> with an
     * incomplete type.
     *
     * Note: Later we may add separate order tracking here (a multi-index
     * type of thing.)
     */
    struct Dynamic::ObjectImpl : F14NodeMap<
                Dynamic,
                Dynamic,
                detail::DynamicHasher,
                detail::DynamicKeyEqual> {
    };

    //////////////////////////////////////////////////////////////////////

    // Helper object for creating objects conveniently.  See object and
    // the Dynamic::Dynamic(ObjectMaker&&) ctor.
    struct Dynamic::ObjectMaker {
        friend struct Dynamic;

        explicit ObjectMaker() : val_(Dynamic::object) {
        }

        explicit ObjectMaker(Dynamic key, Dynamic val) : val_(Dynamic::object) {
            val_.insert(std::move(key), std::move(val));
        }

        // Make sure no one tries to save one of these into an lvalue with
        // auto or anything like that.
        ObjectMaker(ObjectMaker &&) = default;

        ObjectMaker(ObjectMaker const &) = delete;

        ObjectMaker &operator=(ObjectMaker const &) = delete;

        ObjectMaker &operator=(ObjectMaker &&) = delete;

        // This returns an rvalue-reference instead of an lvalue-reference
        // to allow constructs like this to moved instead of copied:
        //  Dynamic a = Dynamic::object("a", "b")("c", "d")
        ObjectMaker &&operator()(Dynamic key, Dynamic val) {
            val_.insert(std::move(key), std::move(val));
            return std::move(*this);
        }

    private:
        Dynamic val_;
    };

    inline void Dynamic::array(EmptyArrayTag) {
    }

    template<class... Args>
    inline Dynamic Dynamic::array(Args &&... args) {
        return Dynamic(Array{std::forward<Args>(args)...});
    }

    inline Dynamic::ObjectMaker Dynamic::object() {
        return ObjectMaker();
    }

    inline Dynamic::ObjectMaker Dynamic::object(Dynamic a, Dynamic b) {
        return ObjectMaker(std::move(a), std::move(b));
    }

    //////////////////////////////////////////////////////////////////////

    struct Dynamic::item_iterator : detail::IteratorAdaptor<
                Dynamic::item_iterator,
                Dynamic::ObjectImpl::iterator,
                std::pair<Dynamic const, Dynamic>,
                std::forward_iterator_tag> {
        using Super = detail::IteratorAdaptor<
            Dynamic::item_iterator,
            Dynamic::ObjectImpl::iterator,
            std::pair<Dynamic const, Dynamic>,
            std::forward_iterator_tag>;

        item_iterator() = default;

        /* implicit */
        item_iterator(Dynamic::ObjectImpl::iterator b) : Super(b) {
        }

        using object_type = Dynamic::ObjectImpl;
    };

    struct Dynamic::value_iterator : detail::IteratorAdaptor<
                Dynamic::value_iterator,
                Dynamic::ObjectImpl::iterator,
                Dynamic,
                std::forward_iterator_tag> {
        using Super = detail::IteratorAdaptor<
            Dynamic::value_iterator,
            Dynamic::ObjectImpl::iterator,
            Dynamic,
            std::forward_iterator_tag>;

        value_iterator() = default;

        /* implicit */
        value_iterator(Dynamic::ObjectImpl::iterator b) : Super(b) {
        }

        using object_type = Dynamic::ObjectImpl;

        Dynamic &dereference() const { return base()->second; }
    };

    struct Dynamic::const_item_iterator
            : detail::IteratorAdaptor<
                Dynamic::const_item_iterator,
                Dynamic::ObjectImpl::const_iterator,
                std::pair<Dynamic const, Dynamic> const,
                std::forward_iterator_tag> {
        using Super = detail::IteratorAdaptor<
            Dynamic::const_item_iterator,
            Dynamic::ObjectImpl::const_iterator,
            std::pair<Dynamic const, Dynamic> const,
            std::forward_iterator_tag>;

        const_item_iterator() = default;

        /* implicit */
        const_item_iterator(Dynamic::ObjectImpl::const_iterator b)
            : Super(b) {
        }

        /* implicit */
        const_item_iterator(item_iterator i) : Super(i.base()) {
        }

        using object_type = Dynamic::ObjectImpl const;
    };

    struct Dynamic::const_key_iterator : detail::IteratorAdaptor<
                Dynamic::const_key_iterator,
                Dynamic::ObjectImpl::const_iterator,
                Dynamic const,
                std::forward_iterator_tag> {
        using Super = detail::IteratorAdaptor<
            Dynamic::const_key_iterator,
            Dynamic::ObjectImpl::const_iterator,
            Dynamic const,
            std::forward_iterator_tag>;

        const_key_iterator() = default;

        /* implicit */
        const_key_iterator(Dynamic::ObjectImpl::const_iterator b)
            : Super(b) {
        }

        using object_type = Dynamic::ObjectImpl const;

        Dynamic const &dereference() const { return base()->first; }
    };

    struct Dynamic::const_value_iterator : detail::IteratorAdaptor<
                Dynamic::const_value_iterator,
                Dynamic::ObjectImpl::const_iterator,
                Dynamic const,
                std::forward_iterator_tag> {
        using Super = detail::IteratorAdaptor<
            Dynamic::const_value_iterator,
            Dynamic::ObjectImpl::const_iterator,
            Dynamic const,
            std::forward_iterator_tag>;

        const_value_iterator() = default;

        /* implicit */
        const_value_iterator(Dynamic::ObjectImpl::const_iterator b)
            : Super(b) {
        }

        /* implicit */
        const_value_iterator(value_iterator i) : Super(i.base()) {
        }

        /* implicit */
        const_value_iterator(Dynamic::ObjectImpl::iterator i)
            : Super(i) {
        }

        using object_type = Dynamic::ObjectImpl const;

        Dynamic const &dereference() const { return base()->second; }
    };

    //////////////////////////////////////////////////////////////////////

    inline Dynamic::Dynamic() : Dynamic(nullptr) {
    }

    inline Dynamic::Dynamic(std::nullptr_t) : type_(NULLT) {
    }

    inline Dynamic::Dynamic(void (*)(EmptyArrayTag)) : type_(ARRAY) {
        new(&u_.array) Array();
    }

    inline Dynamic::Dynamic(ObjectMaker (*)()) : type_(OBJECT) {
        new(getAddress<ObjectImpl>()) ObjectImpl();
    }

    inline Dynamic::Dynamic(char const *s) : type_(STRING) {
        new(&u_.string) std::string(s);
    }

    inline Dynamic::Dynamic(std::string s) : type_(STRING) {
        new(&u_.string) std::string(std::move(s));
    }

    template<typename Stringish, typename>
    inline Dynamic::Dynamic(Stringish &&s) : type_(STRING) {
        new(&u_.string) std::string(s.data(), s.size());
    }

    inline Dynamic::Dynamic(ObjectMaker &&maker) : type_(OBJECT) {
        new(getAddress<ObjectImpl>())
                ObjectImpl(std::move(*maker.val_.getAddress<ObjectImpl>()));
    }

    inline Dynamic::~Dynamic() noexcept {
        destroy();
    }

    // Integral types except bool convert to int64_t, float types to double.
    template<class T>
    struct Dynamic::NumericTypeHelper<
                T,
                typename std::enable_if<std::is_integral<T>::value>::type> {
        static_assert(
            !kIsObjC || sizeof(T) > sizeof(char),
            "char-sized types are ambiguous in objc; cast to bool or wider type");
        using type = int64_t;
    };

    template<>
    struct Dynamic::NumericTypeHelper<bool> {
        using type = bool;
    };

    template<>
    struct Dynamic::NumericTypeHelper<float> {
        using type = double;
    };

    template<>
    struct Dynamic::NumericTypeHelper<double> {
        using type = double;
    };

    inline Dynamic::Dynamic(std::vector<bool>::reference b)
        : Dynamic(static_cast<bool>(b)) {
    }

    inline Dynamic::Dynamic(VectorBoolConstRefCtorType b)
        : Dynamic(static_cast<bool>(b)) {
    }

    template<
        class T,
        class NumericType /* = typename NumericTypeHelper<T>::type */>
    Dynamic::Dynamic(T t) {
        type_ = TypeInfo<NumericType>::type;
        new(getAddress<NumericType>()) NumericType(NumericType(t));
    }

    template<class Iterator>
    Dynamic::Dynamic(Iterator first, Iterator last) : type_(ARRAY) {
        new(&u_.array) Array(first, last);
    }

    template<
        class T,
        class NumericType /* = typename NumericTypeHelper<T>::type */>
    Dynamic &Dynamic::operator=(T t) {
        const auto newType = TypeInfo<NumericType>::type;
        if (type_ == newType) {
            *getAddress<NumericType>() = t;
        } else {
            destroy();
            new(getAddress<NumericType>()) NumericType(t);
            type_ = newType;
        }
        return *this;
    }

    //////////////////////////////////////////////////////////////////////

    inline Dynamic::const_iterator Dynamic::begin() const {
        return get<Array>().begin();
    }

    inline Dynamic::const_iterator Dynamic::end() const {
        return get<Array>().end();
    }

    inline Dynamic::iterator Dynamic::begin() {
        return get<Array>().begin();
    }

    inline Dynamic::iterator Dynamic::end() {
        return get<Array>().end();
    }

    template<class It>
    struct Dynamic::IterableProxy {
        typedef It iterator;
        typedef typename It::value_type value_type;
        typedef typename It::object_type object_type;

        /* implicit */
        IterableProxy(object_type *o) : o_(o) {
        }

        It begin() const { return o_->begin(); }

        It end() const { return o_->end(); }

    private:
        object_type *o_;
    };

    inline Dynamic::IterableProxy<Dynamic::const_key_iterator> Dynamic::keys()
    const {
        return &(get<ObjectImpl>());
    }

    inline Dynamic::IterableProxy<Dynamic::const_value_iterator> Dynamic::values()
    const {
        return &(get<ObjectImpl>());
    }

    inline Dynamic::IterableProxy<Dynamic::const_item_iterator> Dynamic::items()
    const {
        return &(get<ObjectImpl>());
    }

    inline Dynamic::IterableProxy<Dynamic::value_iterator> Dynamic::values() {
        return &(get<ObjectImpl>());
    }

    inline Dynamic::IterableProxy<Dynamic::item_iterator> Dynamic::items() {
        return &(get<ObjectImpl>());
    }

    inline bool Dynamic::isString() const {
        return get_nothrow<std::string>() != nullptr;
    }

    inline bool Dynamic::isObject() const {
        return get_nothrow<ObjectImpl>() != nullptr;
    }

    inline bool Dynamic::isBool() const {
        return get_nothrow<bool>() != nullptr;
    }

    inline bool Dynamic::isArray() const {
        return get_nothrow<Array>() != nullptr;
    }

    inline bool Dynamic::isDouble() const {
        return get_nothrow<double>() != nullptr;
    }

    inline bool Dynamic::isInt() const {
        return get_nothrow<int64_t>() != nullptr;
    }

    inline bool Dynamic::isNull() const {
        return get_nothrow<std::nullptr_t>() != nullptr;
    }

    inline bool Dynamic::isNumber() const {
        return isInt() || isDouble();
    }

    inline Dynamic::Type Dynamic::type() const {
        return type_;
    }

    inline std::string Dynamic::asString() const {
        return asImpl<std::string>();
    }

    inline double Dynamic::asDouble() const {
        return asImpl<double>();
    }

    inline int64_t Dynamic::asInt() const {
        return asImpl<int64_t>();
    }

    inline bool Dynamic::asBool() const {
        return asImpl<bool>();
    }

    inline const std::string &Dynamic::getString() const & {
        return get<std::string>();
    }

    inline double Dynamic::getDouble() const & {
        return get<double>();
    }

    inline int64_t Dynamic::getInt() const & {
        return get<int64_t>();
    }

    inline bool Dynamic::getBool() const & {
        return get<bool>();
    }

    inline std::string &Dynamic::getString() & {
        return get<std::string>();
    }

    inline double &Dynamic::getDouble() & {
        return get<double>();
    }

    inline int64_t &Dynamic::getInt() & {
        return get<int64_t>();
    }

    inline bool &Dynamic::getBool() & {
        return get<bool>();
    }

    inline std::string &&Dynamic::getString() && {
        return std::move(get<std::string>());
    }

    inline double Dynamic::getDouble() && {
        return get<double>();
    }

    inline int64_t Dynamic::getInt() && {
        return get<int64_t>();
    }

    inline bool Dynamic::getBool() && {
        return get<bool>();
    }

    inline const char *Dynamic::c_str() const & {
        return get<std::string>().c_str();
    }

    inline StringPiece Dynamic::stringPiece() const {
        return get<std::string>();
    }

    template<class T>
    struct Dynamic::CompareOp {
        static bool comp(T const &a, T const &b) { return a < b; }
    };

    template<>
    struct Dynamic::CompareOp<Dynamic::ObjectImpl> {
        static bool comp(ObjectImpl const &, ObjectImpl const &) {
            // This code never executes; it is just here for the compiler.
            return false;
        }
    };

    template<>
    struct Dynamic::CompareOp<std::nullptr_t> {
        static bool comp(std::nullptr_t const &, std::nullptr_t const &) {
            return false;
        }
    };

    inline Dynamic &Dynamic::operator+=(Dynamic const &o) {
        if (type() == STRING && o.type() == STRING) {
            *getAddress<std::string>() += *o.getAddress<std::string>();
            return *this;
        }
        *this = detail::numericOp<std::plus>(*this, o);
        return *this;
    }

    inline Dynamic &Dynamic::operator-=(Dynamic const &o) {
        *this = detail::numericOp<std::minus>(*this, o);
        return *this;
    }

    inline Dynamic &Dynamic::operator*=(Dynamic const &o) {
        *this = detail::numericOp<std::multiplies>(*this, o);
        return *this;
    }

    inline Dynamic &Dynamic::operator/=(Dynamic const &o) {
        *this = detail::numericOp<std::divides>(*this, o);
        return *this;
    }

#define FB_DYNAMIC_INTEGER_OP(op)                            \
  inline Dynamic& Dynamic::operator op(Dynamic const& o) {   \
    if (!isInt() || !o.isInt()) {                            \
      throw_exception<TypeError>("int64", type(), o.type()); \
    }                                                        \
    *getAddress<int64_t>() op o.asInt();                     \
    return *this;                                            \
  }

    FB_DYNAMIC_INTEGER_OP(%=)
    FB_DYNAMIC_INTEGER_OP(|=)
    FB_DYNAMIC_INTEGER_OP(&=)
    FB_DYNAMIC_INTEGER_OP(^=)

#undef FB_DYNAMIC_INTEGER_OP

    inline Dynamic &Dynamic::operator++() {
        ++get<int64_t>();
        return *this;
    }

    inline Dynamic &Dynamic::operator--() {
        --get<int64_t>();
        return *this;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic const &> Dynamic::operator[](
        K &&idx) const & {
        return at(std::forward<K>(idx));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &> Dynamic::operator[](
        K &&idx) & {
        if (!isObject() && !isArray()) {
            throw_exception<TypeError>("object/array", type());
        }
        if (isArray()) {
            return at(std::forward<K>(idx));
        }
        auto &obj = get<ObjectImpl>();
        auto ret = obj.emplace(std::forward<K>(idx), nullptr);
        return ret.first->second;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &&> Dynamic::operator[](
        K &&idx) && {
        return std::move((*this)[std::forward<K>(idx)]);
    }

    inline Dynamic const &Dynamic::operator[](StringPiece k) const & {
        return at(k);
    }

    inline Dynamic &&Dynamic::operator[](StringPiece k) && {
        return std::move((*this)[k]);
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic> Dynamic::getDefault(
        K &&k, const Dynamic &v) const & {
        auto &obj = get<ObjectImpl>();
        auto it = obj.find(std::forward<K>(k));
        return it == obj.end() ? v : it->second;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic> Dynamic::getDefault(
        K &&k, Dynamic &&v) const & {
        auto &obj = get<ObjectImpl>();
        auto it = obj.find(std::forward<K>(k));
        // Avoid clang bug with ternary
        if (it == obj.end()) {
            return std::move(v);
        } else {
            return it->second;
        }
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic> Dynamic::getDefault(
        K &&k, const Dynamic &v) && {
        auto &obj = get<ObjectImpl>();
        auto it = obj.find(std::forward<K>(k));
        // Avoid clang bug with ternary
        if (it == obj.end()) {
            return v;
        } else {
            return std::move(it->second);
        }
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic> Dynamic::getDefault(
        K &&k, Dynamic &&v) && {
        auto &obj = get<ObjectImpl>();
        auto it = obj.find(std::forward<K>(k));
        return std::move(it == obj.end() ? v : it->second);
    }

    template<typename K, typename V>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &> Dynamic::setDefault(
        K &&k, V &&v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(std::forward<K>(k), std::forward<V>(v)).first->second;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &> Dynamic::setDefault(
        K &&k, Dynamic &&v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(std::forward<K>(k), std::move(v)).first->second;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &> Dynamic::setDefault(
        K &&k, const Dynamic &v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(std::forward<K>(k), v).first->second;
    }

    template<typename V>
    Dynamic &Dynamic::setDefault(StringPiece k, V &&v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(k, std::forward<V>(v)).first->second;
    }

    inline Dynamic &Dynamic::setDefault(StringPiece k, Dynamic &&v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(k, std::move(v)).first->second;
    }

    inline Dynamic &Dynamic::setDefault(StringPiece k, const Dynamic &v) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(k, v).first->second;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic const *> Dynamic::get_ptr(
        K &&k) const & {
        return get_ptrImpl(std::forward<K>(k));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic *> Dynamic::get_ptr(
        K &&idx) & {
        return const_cast<Dynamic *>(const_cast<Dynamic const *>(this)->get_ptr(idx));
    }

    inline Dynamic *Dynamic::get_ptr(StringPiece idx) & {
        return const_cast<Dynamic *>(const_cast<Dynamic const *>(this)->get_ptr(idx));
    }

// clang-format off
inline
Dynamic::resolved_json_pointer<Dynamic>
Dynamic::try_get_ptr(json_pointer const& jsonPtr) & {
  auto ret = const_cast<Dynamic const*>(this)->try_get_ptr(jsonPtr);
  if (ret.hasValue()) {
    return json_pointer_resolved_value<Dynamic>{
        const_cast<Dynamic*>(ret.value().parent),
        const_cast<Dynamic*>(ret.value().value),
        ret.value().parent_key, ret.value().parent_index};
  } else {
    return makeUnexpected(
        json_pointer_resolution_error<Dynamic>{
            ret.error().error_code,
            ret.error().index,
            const_cast<Dynamic*>(ret.error().context)}
        );
  }
}
    // clang-format on

    inline Dynamic *Dynamic::get_ptr(json_pointer const &jsonPtr) & {
        return const_cast<Dynamic *>(
            const_cast<Dynamic const *>(this)->get_ptr(jsonPtr));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic const &> Dynamic::at(
        K &&k) const & {
        return atImpl(std::forward<K>(k));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &> Dynamic::at(K &&idx) & {
        return const_cast<Dynamic &>(const_cast<Dynamic const *>(this)->at(idx));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic &&> Dynamic::at(K &&idx) && {
        return std::move(at(idx));
    }

    inline Dynamic &Dynamic::at(StringPiece idx) & {
        return const_cast<Dynamic &>(const_cast<Dynamic const *>(this)->at(idx));
    }

    inline Dynamic &&Dynamic::at(StringPiece idx) && {
        return std::move(at(idx));
    }

    inline bool Dynamic::empty() const {
        if (isNull()) {
            return true;
        }
        return !size();
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic::const_item_iterator>
    Dynamic::find(K &&key) const {
        return get<ObjectImpl>().find(std::forward<K>(key));
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, Dynamic::item_iterator>
    Dynamic::find(K &&key) {
        return get<ObjectImpl>().find(std::forward<K>(key));
    }

    inline Dynamic::const_item_iterator Dynamic::find(StringPiece key) const {
        return get<ObjectImpl>().find(key);
    }

    inline Dynamic::item_iterator Dynamic::find(StringPiece key) {
        return get<ObjectImpl>().find(key);
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, std::size_t> Dynamic::count(
        K &&key) const {
        return find(std::forward<K>(key)) != items().end() ? 1u : 0u;
    }

    inline std::size_t Dynamic::count(StringPiece key) const {
        return find(key) != items().end() ? 1u : 0u;
    }

    template<class K, class V>
    inline Dynamic::IfNotIterator<K, void> Dynamic::insert(K &&key, V &&val) {
        auto &obj = get<ObjectImpl>();
        obj[std::forward<K>(key)] = std::forward<V>(val);
    }

    template<class... Args>
    inline std::pair<Dynamic::item_iterator, bool> Dynamic::emplace(
        Args &&... args) {
        auto &obj = get<ObjectImpl>();
        return obj.emplace(std::forward<Args>(args)...);
    }

    template<class K, class... Args>
    inline std::pair<Dynamic::item_iterator, bool> Dynamic::try_emplace(
        K &&key, Args &&... args) {
        auto &obj = get<ObjectImpl>();
        return obj.try_emplace(std::forward<K>(key), std::forward<Args>(args)...);
    }

    template<class T>
    inline Dynamic::iterator Dynamic::insert(const_iterator pos, T &&value) {
        auto &arr = get<Array>();
        return arr.insert(pos, std::forward<T>(value));
    }

    template<class InputIt>
    inline Dynamic::iterator Dynamic::insert(
        const_iterator pos, InputIt first, InputIt last) {
        auto &arr = get<Array>();
        return arr.insert(pos, first, last);
    }

    inline void Dynamic::update(const Dynamic &mergeObj) {
        if (!isObject() || !mergeObj.isObject()) {
            throw_exception<TypeError>("object", type(), mergeObj.type());
        }

        for (const auto &pair: mergeObj.items()) {
            (*this)[pair.first] = pair.second;
        }
    }

    inline void Dynamic::update_missing(const Dynamic &mergeObj1) {
        if (!isObject() || !mergeObj1.isObject()) {
            throw_exception<TypeError>("object", type(), mergeObj1.type());
        }

        // Only add if not already there
        for (const auto &pair: mergeObj1.items()) {
            if ((*this).find(pair.first) == (*this).items().end()) {
                (*this)[pair.first] = pair.second;
            }
        }
    }

    inline void Dynamic::merge_patch(const Dynamic &patch) {
        auto &self = *this;
        if (!patch.isObject()) {
            self = patch;
            return;
        }
        // if we are not an object, erase all contents, reset to object
        if (!isObject()) {
            self = object;
        }
        for (const auto &pair: patch.items()) {
            if (pair.second.isNull()) {
                // if name could be found in current object, remove it
                auto it = self.find(pair.first);
                if (it != self.items().end()) {
                    self.erase(it);
                }
            } else {
                self[pair.first].merge_patch(pair.second);
            }
        }
    }

    inline Dynamic Dynamic::merge(
        const Dynamic &mergeObj1, const Dynamic &mergeObj2) {
        // No checks on type needed here because they are done in update_missing
        // Note that we do update_missing here instead of update() because
        // it will prevent the extra writes that would occur with update()
        auto ret = mergeObj2;
        ret.update_missing(mergeObj1);
        return ret;
    }

    template<typename K>
    Dynamic::IfIsNonStringDynamicConvertible<K, std::size_t> Dynamic::erase(
        K &&key) {
        auto &obj = get<ObjectImpl>();
        return obj.erase(std::forward<K>(key));
    }

    inline std::size_t Dynamic::erase(StringPiece key) {
        auto &obj = get<ObjectImpl>();
        return obj.erase(key);
    }

    inline Dynamic::iterator Dynamic::erase(const_iterator it) {
        auto &arr = get<Array>();
        // std::vector doesn't have an erase method that works on const iterators,
        // even though the standard says it should, so this hack converts to a
        // non-const iterator before calling erase.
        return get<Array>().erase(arr.begin() + (it - arr.begin()));
    }

    inline Dynamic::const_key_iterator Dynamic::erase(const_key_iterator it) {
        return const_key_iterator(get<ObjectImpl>().erase(it.base()));
    }

    inline Dynamic::const_key_iterator Dynamic::erase(
        const_key_iterator first, const_key_iterator last) {
        return const_key_iterator(get<ObjectImpl>().erase(first.base(), last.base()));
    }

    inline Dynamic::value_iterator Dynamic::erase(const_value_iterator it) {
        return value_iterator(get<ObjectImpl>().erase(it.base()));
    }

    inline Dynamic::value_iterator Dynamic::erase(
        const_value_iterator first, const_value_iterator last) {
        return value_iterator(get<ObjectImpl>().erase(first.base(), last.base()));
    }

    inline Dynamic::item_iterator Dynamic::erase(const_item_iterator it) {
        return item_iterator(get<ObjectImpl>().erase(it.base()));
    }

    inline Dynamic::item_iterator Dynamic::erase(
        const_item_iterator first, const_item_iterator last) {
        return item_iterator(get<ObjectImpl>().erase(first.base(), last.base()));
    }

    inline void Dynamic::resize(std::size_t sz, Dynamic const &c) {
        auto &arr = get<Array>();
        arr.resize(sz, c);
    }

    inline void Dynamic::push_back(Dynamic const &v) {
        auto &arr = get<Array>();
        arr.push_back(v);
    }

    inline void Dynamic::push_back(Dynamic &&v) {
        auto &arr = get<Array>();
        arr.push_back(std::move(v));
    }

    inline void Dynamic::pop_back() {
        auto &arr = get<Array>();
        arr.pop_back();
    }

    inline const Dynamic &Dynamic::back() const {
        auto &arr = get<Array>();
        return arr.back();
    }

    //////////////////////////////////////////////////////////////////////

    inline Dynamic::Dynamic(Array &&r) : type_(ARRAY) {
        new(&u_.array) Array(std::move(r));
    }

#define MELON_DYNAMIC_DEC_TYPEINFO(T, val)     \
  template <>                                  \
  struct Dynamic::TypeInfo<T> {                \
    static const char* const name;             \
    static constexpr Dynamic::Type type = val; \
  };                                           \
  //

    MELON_DYNAMIC_DEC_TYPEINFO(std::nullptr_t, Dynamic::NULLT)

    MELON_DYNAMIC_DEC_TYPEINFO(bool, Dynamic::BOOL)

    MELON_DYNAMIC_DEC_TYPEINFO(std::string, Dynamic::STRING)

    MELON_DYNAMIC_DEC_TYPEINFO(Dynamic::Array, Dynamic::ARRAY)

    MELON_DYNAMIC_DEC_TYPEINFO(double, Dynamic::DOUBLE)

    MELON_DYNAMIC_DEC_TYPEINFO(int64_t, Dynamic::INT64)

    MELON_DYNAMIC_DEC_TYPEINFO(Dynamic::ObjectImpl, Dynamic::OBJECT)

#undef MELON_DYNAMIC_DEC_TYPEINFO

    template<class T>
    T Dynamic::asImpl() const {
        MELON_PUSH_WARNING
        MELON_CLANG_DISABLE_WARNING("-Wcovered-switch-default")
        switch (type()) {
            case INT64:
                return to<T>(*get_nothrow<int64_t>());
            case DOUBLE:
                return to<T>(*get_nothrow<double>());
            case BOOL:
                return to<T>(*get_nothrow<bool>());
            case STRING:
                return to<T>(*get_nothrow<std::string>());
            case NULLT:
            case ARRAY:
            case OBJECT:
            default:
                throw_exception<TypeError>("int/double/bool/string", type());
        }
        MELON_POP_WARNING
    }

    // Return a T* to our type, or null if we're not that type.
    template<class T>
    T *Dynamic::get_nothrow() & noexcept {
        if (type_ != TypeInfo<T>::type) {
            return nullptr;
        }
        return getAddress<T>();
    }

    template<class T>
    T const *Dynamic::get_nothrow() const & noexcept {
        return const_cast<Dynamic *>(this)->get_nothrow<T>();
    }

    // Return T* for where we can put a T, without type checking.  (Memory
    // might be uninitialized, even.)
    template<class T>
    T *Dynamic::getAddress() noexcept {
        return GetAddrImpl<T>::get(u_);
    }

    template<class T>
    T const *Dynamic::getAddress() const noexcept {
        return const_cast<Dynamic *>(this)->getAddress<T>();
    }

    template<class T>
    struct Dynamic::GetAddrImpl {
    };

    template<>
    struct Dynamic::GetAddrImpl<std::nullptr_t> {
        static std::nullptr_t *get(Data &d) noexcept { return &d.nul; }
    };

    template<>
    struct Dynamic::GetAddrImpl<Dynamic::Array> {
        static Array *get(Data &d) noexcept { return &d.array; }
    };

    template<>
    struct Dynamic::GetAddrImpl<bool> {
        static bool *get(Data &d) noexcept { return &d.boolean; }
    };

    template<>
    struct Dynamic::GetAddrImpl<int64_t> {
        static int64_t *get(Data &d) noexcept { return &d.integer; }
    };

    template<>
    struct Dynamic::GetAddrImpl<double> {
        static double *get(Data &d) noexcept { return &d.doubl; }
    };

    template<>
    struct Dynamic::GetAddrImpl<std::string> {
        static std::string *get(Data &d) noexcept { return &d.string; }
    };

    template<>
    struct Dynamic::GetAddrImpl<Dynamic::ObjectImpl> {
        static_assert(
            sizeof(ObjectImpl) <= sizeof(Data::objectBuffer),
            "In your implementation, F14NodeMap<> apparently takes different"
            " amount of space depending on its template parameters.  This is "
            "weird.  Make objectBuffer bigger if you want to compile Dynamic.");

        static ObjectImpl *get(Data &d) noexcept {
            void *data = &d.objectBuffer;
            return static_cast<ObjectImpl *>(data);
        }
    };

    template<class T>
    T &Dynamic::get() {
        if (auto *p = get_nothrow<T>()) {
            return *p;
        }
        throw_exception<TypeError>(TypeInfo<T>::name, type());
    }

    template<class T>
    T const &Dynamic::get() const {
        return const_cast<Dynamic *>(this)->get<T>();
    }

    //////////////////////////////////////////////////////////////////////

    /*
     * Helper for implementing operator<<.  Throws if the type shouldn't
     * support it.
     */
    template<class T>
    struct Dynamic::PrintImpl {
        static void print(Dynamic const &, std::ostream &out, T const &t) { out << t; }
    };

    // Otherwise, null, being (void*)0, would print as 0.
    template<>
    struct Dynamic::PrintImpl<std::nullptr_t> {
        static void print(
            Dynamic const & /* d */, std::ostream &out, std::nullptr_t const &) {
            out << "null";
        }
    };

    template<>
    struct Dynamic::PrintImpl<Dynamic::ObjectImpl> {
        static void print(
            Dynamic const &d, std::ostream &out, Dynamic::ObjectImpl const &) {
            d.print_as_pseudo_json(out);
        }
    };

    template<>
    struct Dynamic::PrintImpl<Dynamic::Array> {
        static void print(
            Dynamic const &d, std::ostream &out, Dynamic::Array const &) {
            d.print_as_pseudo_json(out);
        }
    };

    inline void Dynamic::print(std::ostream &out) const {
#define FB_X(T) PrintImpl<T>::print(*this, out, *getAddress<T>())
        FB_DYNAMIC_APPLY(type_, FB_X);
#undef FB_X
    }

    inline std::ostream &operator<<(std::ostream &out, Dynamic const &d) {
        d.print(out);
        return out;
    }

    //////////////////////////////////////////////////////////////////////

    inline const_dynamic_view::const_dynamic_view(Dynamic const &d) noexcept
        : d_(&d) {
    }

    inline const_dynamic_view::const_dynamic_view(Dynamic const *d) noexcept
        : d_(d) {
    }

    inline const_dynamic_view::operator bool() const noexcept {
        return !empty();
    }

    inline bool const_dynamic_view::empty() const noexcept {
        return d_ == nullptr;
    }

    inline void const_dynamic_view::reset() noexcept {
        d_ = nullptr;
    }

    template<typename Key, typename... Keys>
    inline const_dynamic_view const_dynamic_view::descend(
        Key const &key, Keys const &... keys) const noexcept {
        return descend_(key, keys...);
    }

    template<typename Key1, typename Key2, typename... Keys>
    inline Dynamic const *const_dynamic_view::descend_(
        Key1 const &key1, Key2 const &key2, Keys const &... keys) const noexcept {
        if (!d_) {
            return nullptr;
        }
        return const_dynamic_view{descend_unchecked_(key1)}.descend_(key2, keys...);
    }

    template<typename Key>
    inline Dynamic const *const_dynamic_view::descend_(
        Key const &key) const noexcept {
        if (!d_) {
            return nullptr;
        }
        return descend_unchecked_(key);
    }

    template<typename Key>
    inline Dynamic::IfIsNonStringDynamicConvertible<Key, Dynamic const *>
    const_dynamic_view::descend_unchecked_(Key const &key) const noexcept {
        if (auto *parray = d_->get_nothrow<Dynamic::Array>()) {
            if /* constexpr */ (!std::is_integral<Key>::value) {
                return nullptr;
            }
            if (key < 0 || melon::to_unsigned(key) >= parray->size()) {
                return nullptr;
            }
            return &(*parray)[size_t(key)];
        } else if (auto *pobject = d_->get_nothrow<Dynamic::ObjectImpl>()) {
            auto it = pobject->find(key);
            if (it == pobject->end()) {
                return nullptr;
            }
            return &it->second;
        }
        return nullptr;
    }

    inline Dynamic const *const_dynamic_view::descend_unchecked_(
        melon::StringPiece key) const noexcept {
        if (auto *pobject = d_->get_nothrow<Dynamic::ObjectImpl>()) {
            auto it = pobject->find(key);
            if (it == pobject->end()) {
                return nullptr;
            }
            return &it->second;
        }
        return nullptr;
    }

    inline Dynamic const_dynamic_view::value_or(Dynamic &&val) const {
        if (d_) {
            return *d_;
        }
        return std::move(val);
    }

    template<typename T, typename... Args>
    inline T const_dynamic_view::get_copy(Args &&... args) const {
        if (auto *v = (d_ ? d_->get_nothrow<T>() : nullptr)) {
            return *v;
        }
        return T(std::forward<Args>(args)...);
    }

    inline std::string const_dynamic_view::string_or(char const *val) const {
        return get_copy<std::string>(val);
    }

    inline std::string const_dynamic_view::string_or(std::string val) const {
        return get_copy<std::string>(std::move(val));
    }

    // Specialized version for StringPiece, FixedString, and other types which are
    // not convertible to std::string, but can construct one from .data and .size
    // to std::string. Will not trigger a copy unless data and size require it.
    template<typename Stringish, typename>
    inline std::string const_dynamic_view::string_or(Stringish &&val) const {
        return get_copy(val.data(), val.size());
    }

    inline double const_dynamic_view::double_or(double val) const noexcept {
        return get_copy<double>(val);
    }

    inline int64_t const_dynamic_view::int_or(int64_t val) const noexcept {
        return get_copy<int64_t>(val);
    }

    inline bool const_dynamic_view::bool_or(bool val) const noexcept {
        return get_copy<bool>(val);
    }

    inline dynamic_view::dynamic_view(Dynamic &d) noexcept
        : const_dynamic_view(d) {
    }

    template<typename Key, typename... Keys>
    inline dynamic_view dynamic_view::descend(
        Key const &key, Keys const &... keys) const noexcept {
        if (auto *child = const_dynamic_view::descend_(key, keys...)) {
            return *const_cast<Dynamic *>(child);
        }
        return {};
    }

    inline Dynamic dynamic_view::move_value_or(Dynamic &&val) noexcept {
        if (d_) {
            return std::move(*const_cast<Dynamic *>(d_));
        }
        return std::move(val);
    }

    template<typename T, typename... Args>
    inline T dynamic_view::get_move(Args &&... args) {
        if (auto *v = (d_ ? const_cast<Dynamic *>(d_)->get_nothrow<T>() : nullptr)) {
            return std::move(*v);
        }
        return T(std::forward<Args>(args)...);
    }

    inline std::string dynamic_view::move_string_or(char const *val) {
        return get_move<std::string>(val);
    }

    inline std::string dynamic_view::move_string_or(std::string val) noexcept {
        return get_move<std::string>(std::move(val));
    }

    template<typename Stringish, typename>
    inline std::string dynamic_view::move_string_or(Stringish &&val) {
        return get_move<std::string>(val.begin(), val.end());
    }

    //////////////////////////////////////////////////////////////////////

    // Specialization of FormatValue so Dynamic objects can be formatted
    template<>
    class FormatValue<Dynamic> {
    public:
        explicit FormatValue(const Dynamic &val) : val_(val) {
        }

        template<class FormatCallback>
        void format(FormatArg &arg, FormatCallback &cb) const {
            switch (val_.type()) {
                case Dynamic::NULLT:
                    FormatValue<std::nullptr_t>(nullptr).format(arg, cb);
                    break;
                case Dynamic::BOOL:
                    FormatValue<bool>(val_.asBool()).format(arg, cb);
                    break;
                case Dynamic::INT64:
                    FormatValue<int64_t>(val_.asInt()).format(arg, cb);
                    break;
                case Dynamic::STRING:
                    FormatValue<std::string>(val_.asString()).format(arg, cb);
                    break;
                case Dynamic::DOUBLE:
                    FormatValue<double>(val_.asDouble()).format(arg, cb);
                    break;
                case Dynamic::ARRAY:
                    FormatValue(val_.at(arg.splitIntKey())).format(arg, cb);
                    break;
                case Dynamic::OBJECT:
                    FormatValue(val_.at(arg.splitKey().toString())).format(arg, cb);
                    break;
            }
        }

    private:
        const Dynamic &val_;
    };

    template<class V>
    class FormatValue<detail::DefaultValueWrapper<Dynamic, V> > {
    public:
        explicit FormatValue(const detail::DefaultValueWrapper<Dynamic, V> &val)
            : val_(val) {
        }

        template<class FormatCallback>
        void format(FormatArg &arg, FormatCallback &cb) const {
            auto &c = val_.container;
            switch (c.type()) {
                case Dynamic::NULLT:
                case Dynamic::BOOL:
                case Dynamic::INT64:
                case Dynamic::STRING:
                case Dynamic::DOUBLE:
                    FormatValue<Dynamic>(c).format(arg, cb);
                    break;
                case Dynamic::ARRAY: {
                    int key = arg.splitIntKey();
                    if (key >= 0 && size_t(key) < c.size()) {
                        FormatValue<Dynamic>(c.at(key)).format(arg, cb);
                    } else {
                        FormatValue<V>(val_.defaultValue).format(arg, cb);
                    }
                    break;
                }
                case Dynamic::OBJECT: {
                    auto pos = c.find(arg.splitKey());
                    if (pos != c.items().end()) {
                        FormatValue<Dynamic>(pos->second).format(arg, cb);
                    } else {
                        FormatValue<V>(val_.defaultValue).format(arg, cb);
                    }
                    break;
                }
            }
        }

    private:
        const detail::DefaultValueWrapper<Dynamic, V> &val_;
    };
} // namespace melon

#undef FB_DYNAMIC_APPLY
